#include "hashmap.h"
#include <malloc.h>

static unsigned default_hashcode(hashmap_t *map, void *key);
static bool default_equals(void *k1, void *k2);
static void default_put(hashmap_t *map, void *key, void *value);
static void *default_get(hashmap_t *map, void *key);
static bool default_remove(hashmap_t *map, void *key);
static void default_clear(hashmap_t *map);
static bool default_exists(hashmap_t *map, void *key);

// BKDR hash
unsigned str_hashcode(hashmap_t *map, void *key) {
  unsigned seed = 131;
  unsigned hash = 0;

  char *ptr = key;

  while (*ptr) {
    hash = hash * seed + (*ptr++);
  }

  return hash & 0x7fffffff;
}

unsigned default_hashcode(hashmap_t *map, void *key) { return (long)key; }

void reset_hashmap(hashmap_t *map, int cap) {
  if (cap < 8) {
    return;
  }

  // 键值对临时存储空间
  entry_t *tmp_list = malloc(map->size * sizeof(entry_t));

  hashmap_iter_t *iter = create_hashmap_iter(map);
  int length = map->size;

  for (int index = 0; has_next_hashmap_iter(iter); index++) {
    // 迭代取出所有键值对
    iter = next_hashamp_iter(iter);
    tmp_list[index].key = iter->entry->key;
    tmp_list[index].value = iter->entry->value;
    tmp_list[index].next = NULL;
  }

  free_hashmap_iter(&iter);

  // 清除原有键值对数据
  map->size = 0;
  for (int i = 0; i < map->cap; i++) {
    entry_t *current = &map->entry_list[i];
    current->key = NULL;
    current->value = NULL;
    if (current->next != NULL) {
      while (current->next != NULL) {
        entry_t *temp = current->next->next;
        free(current->next);
        current->next = temp;
      }
    }
  }

  map->cap = cap;

  entry_t *relist =
      (entry_t *)realloc(map->entry_list, map->cap * sizeof(entry_t));

  if (relist != NULL) {
    map->entry_list = relist;
    relist = NULL;
  }

  // 初始化数据
  for (int i = 0; i < map->cap; i++) {
    map->entry_list[i].key = NULL;
    map->entry_list[i].value = NULL;
    map->entry_list[i].next = NULL;
  }

  // 将所有键值对重新写入内存
  for (int i = 0; i < length; i++) {
    map->put(map, tmp_list[i].key, tmp_list[i].value);
  }
  free(tmp_list);
}

void default_put(hashmap_t *map, void *key, void *value) {
  if (map->auto_assign && map->size >= map->cap) {
    reset_hashmap(map, map->cap * 2);
  }

  int index = map->hashcode(map, key) % map->cap;

  if (map->entry_list[index].key == NULL) {
    ++map->size;
    map->entry_list[index].key = key;
    map->entry_list[index].value = value;
  } else {
    entry_t *cur = &map->entry_list[index];
    while (!cur) {
      if (map->equals(key, cur->key)) {
        cur->value = value;
        return;
      }

      cur = cur->next;
    }

    entry_t *e = malloc(sizeof(entry_t));
    e->key = key;
    e->value = value;
    e->next = map->entry_list[index].next;
    map->entry_list[index].next = e;
    ++map->size;
  }
}

void *default_get(hashmap_t *map, void *key) {
  int index = map->hashcode(map, key) % map->cap;
  entry_t *e = &map->entry_list[index];

  while (e->key && !map->equals(e->key, key)) {
    e = e->next;
  }

  return e->value;
}

bool default_remove(hashmap_t *map, void *key) {
  int index = map->hashcode(map, key) % map->cap;

  entry_t *e = &map->entry_list[index];

  if (!e->key) {
    return false;
  }

  bool ret = true;

  if (map->equals(e->key, key)) {
    --map->size;
    if (e->next) {
      entry_t *tmp = e->next;
      *e = *tmp;
      free(tmp);
    } else {
      e->key = e->value = NULL;
    }

    ret = true;
  } else {
    entry_t *p = e;
    e = e->next;
    while (e) {
      if (map->equals(e->key, key)) {
        --map->size;
        p->next = e->next;
        free(e);
        ret = true;
        break;
      }

      p = e;
      e = e->next;
    }
  }

  if (ret && map->auto_assign && map->size < map->cap / 2) {
    reset_hashmap(map, map->cap * 2);
  }

  return ret;
}

bool default_exists(hashmap_t *map, void *key) {
  int index = map->hashcode(map, key) % map->cap;
  entry_t *entry = &map->entry_list[index];
  if (entry->key == NULL) {
    return false;
  }
  if (map->equals(entry->key, key)) {
    return true;
  }
  if (entry->next != NULL) {
    do {
      if (map->equals(entry->key, key)) {
        return true;
      }
      entry = entry->next;

    } while (entry != NULL);
    return false;
  } else {
    return false;
  }
}

void default_clear(hashmap_t *map) {
  for (int i = 0; i < map->cap; i++) {
    // 释放冲突值内存
    entry_t *entry = map->entry_list[i].next;
    while (entry != NULL) {
      entry_t *next = entry->next;
      free(entry);
      entry = next;
    }
    map->entry_list[i].next = NULL;
  }
  // 释放存储空间
  free(map->entry_list);
  map->entry_list = NULL;
  map->size = -1;
  map->cap = 0;
}

bool default_equals(void *k1, void *k2) { return k1 == k2; }

hashmap_t *create_hashmap(Hashcode hashcode, Equals equals) {
  hashmap_t *map = malloc(sizeof(hashmap_t));
  map->size = 0;
  map->cap = 8;
  map->hashcode = hashcode == NULL ? default_hashcode : hashcode;
  map->equals = (equals == NULL ? default_equals : equals);
  map->exists = default_exists;
  map->get = default_get;
  map->put = default_put;
  map->remove = default_remove;
  map->clear = default_clear;
  map->auto_assign = true;
  // 起始分配8个内存空间，溢出时会自动扩充
  map->entry_list = malloc(map->cap * sizeof(entry_t));

  entry_t *p = map->entry_list;

  for (int i = 0; i < map->size; i++) {
    p[i].key = p[i].value = p[i].next = NULL;
  }
  return map;
}

void free_hashmap(hashmap_t **mapptr) {
  free((*mapptr)->entry_list);
  (*mapptr)->clear(*mapptr);
  *mapptr = NULL;
}

hashmap_iter_t *create_hashmap_iter(hashmap_t *map) {
  hashmap_iter_t *iter = malloc(sizeof(hashmap_iter_t));
  iter->map = map;
  iter->count = 0;
  iter->hashcode = -1;
  iter->entry = NULL;
  return iter;
}

bool has_next_hashmap_iter(hashmap_iter_t *iter) {
  return iter->count < iter->map->size;
}

hashmap_iter_t *next_hashamp_iter(hashmap_iter_t *iter) {
  if (has_next_hashmap_iter(iter)) {
    if (iter->entry != NULL && iter->entry->next != NULL) {
      iter->count++;
      iter->entry = iter->entry->next;
      return iter;
    }

    while (++iter->hashcode < iter->map->size) {
      entry_t *entry = &iter->map->entry_list[iter->hashcode];
      if (entry->key != NULL) {
        iter->count++;
        iter->entry = entry;
        break;
      }
    }
  }
  return iter;
}

void free_hashmap_iter(hashmap_iter_t **iterptr) {
  free(*iterptr);
  *iterptr = NULL;
}
